package LeetCode.leetcode;

import domain.ListNode;
import util.ListNodeUtil;

/**
 * 两两交换链表中的节点
 *
 * @author: leiwenkang02@meituan.com
 * @date: 2018/9/27
 * @time: 19:25
 */
public class Test24两两交换链表中的节点 {
    public static void main(String[] args) {
        ListNode p1 = new ListNode(1);
        ListNode p2 = new ListNode(2);
        ListNode p3 = new ListNode(3);
        ListNode p4 = new ListNode(4);
        ListNode p5 = new ListNode(5);
        p1.next = p2;
        p2.next = p3;
        p3.next = p4;
        p4.next = p5;

        ListNode result = swapPairs(p1);

        ListNodeUtil.printListNode(result);
    }

    /**
     * 1 -> 2 -> 3 -> 4 -> 5
     * 先再其前面加一个辅助节点 0 -> 1 -> 2 -> 3 -> 4 -> 5
     * 第一次遍历，0为pre，1为start，2位end， 交换start和end，交换后结果为 0 -> 2 -> 1 -> 3 -> 4 -> 5
     * 第二次遍历，1为pre，3为start，4位end， 交换start和end，交换后结果为 0 -> 2 -> 1 -> 4 -> 3 -> 5
     * 第三次遍历，3为pre，退出循环
     * @param head
     * @return
     */
    public static ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode temp = pre;
        while(temp.next != null && temp.next.next != null) {
            //详细讲解第一次遍历过程
            //1为start，2为end
            ListNode start = temp.next;
            ListNode end = temp.next.next;

            //0指向2
            temp.next = end;
            //1指向3
            start.next = end.next;
            //2指向1
            end.next = start;

            //temp赋值给1
            temp = start;
        }
        return pre.next;
    }
}
